This invention relates generally to updating computer programs.
With the ever increasing use of remote communication and in particular the Internet, new applications have been introduced such as commercial trade over the Internet, electronic supermarkets, distribution of computer products over the Internet, and others.
Both the popularity and availability of access to the Internet for common users have encouraged not only the distribution of products, but also the upgrade and update of the product under question from a remote site, using, to this end, the Internet infra-structure.
Turning to a specific example of computer programs, an old program is installed at a remote client site and is subject to be upgraded to a new program, where the latter includes some modifications as compared to the old program.
In order to catty out the update at the remote client site (through the network), the provider should, preferably, generate a difference result representative of the difference between the old program and the new program, and send the resulting file through the Internet to the remote client site. The client, in turn, invokes appropriate utility, which incorporates the differences in the old program, thereby generating the desired new program at the client site, The specified procedure caries the obvious advantages in that on the one band, the provider does not need to be present at the client site and, on the other hand, only the difference result and not the entire new program is sent to the client. Assuming, for example, that a modified Office ""97 package (commercially available from Microsoft Inc. USA) should be sent to clients, since the compressed size of programs of the package occupies ten of Mega-bytes, and, further considering the relatively low throughput of the Internet and the bottleneck of the modem throughput at the client end (say an average of 33,600 bps), it is easy to understand that transmitting the entire new package through the network is practically infeasible.
Normally, the volume of the difference result is significantly smaller than that of the raw new program and, accordingly, sending only the difference result data rather than the entire new program, is more efficient. This notwithstanding, and as will be explained in greater detail below, applying known per se file difference applications (such as techniques utilized by diff utilities of the UNIX operating systems or a similar diff utility of the GNU project from FSF) in order to generate a difference result between the old program and the new program, normally results in a relatively large amount of data, even if the modifications that were introduced to the old program (in order to generate the new program) are very few. Thus, consider, for example, an old program where few new instructions are inserted and few others are deleted in order to bring about the new program. The difference result between, the old program and the new program will not only reveal the inserted and deleted instructions, but also all those entries that jump, jump on condition, call functions, reference to data and possibly others (referred to, collectively, as reference entriesxe2x80x94see glossary below) which, by nature, specify a target address (reference) as an integral part of the command. The latter addresses may have been changed due to the fact that some instructions were added and others deleted. It is important to note that the reference entries that are modified are not those that were inserted, and obviously not those that were deleted. In fact, insertion of only one new entry may result in the plurality of altered reference entries which will naturally be reflected in the difference result and obviously will inflate its volume.
It is accordingly appreciated that despite the fact that the actual change between the old and new program is very limited, the resulting file difference is relatively large. The same problem is encountered in other applications, which employ data tables (see Glossary below), that are structured like a program, and are subject to updates in the manner specified.
There is accordingly a need in the art to provide for an efficient tool which will result in significantly smaller volumes of difference results between old programs and new programs, as compared to hitherto known techniques for accomplishing difference result. The proposed tool is useful for various applications including, but not limited to, incremental software updates and version control.
There is yet another need in the art to provide for an efficient tool which will result in significantly smaller volumes of difference results between old data tables and new data tables.
There follows a glossary of terms, some of which are conventional and others have been coined:
Data Tablexe2x80x94a table of entries, each may have a different size;
Entryxe2x80x94a data fable includes entries, each of which is an addressable unit that contains data;
Addressxe2x80x94a number which is uniquely assigned to a single entry by which that entry is accessed; In the following description, the terms entry and address are occasionally used interchangeably.
Referencexe2x80x94a part of the data appearing in an entry in the data table which is used to refer to some other entry from the same data table. A reference can be either an address or a number used to compute an address. Entries that include references are designated also as reference entries.
Labelxe2x80x94an abstract notation of an entry which is referred by another entry of the same data table through a reference.
Old Data Tablexe2x80x94a data table (or portion of a data table) that is to be updated (possibly from remote site) so as to generate a new data table (or portion of a new data table). Insofar as remote update is concerned, it is normally, although not necessarily, transmitted through a communication network such as the Internet. It should be noted that whilst for convenience of explanation only, the description focuses predominately on the Internet, the invention is by no means bound by this specific example.
As an example, a data table can be an executable program either as a loaded program in machine-memory or as an executable-file. In this example, entries are individual machine instructions of the program or the individual data elements used by the program.
Instructions and data elements of a program may contain addresses to other instructions or data elements and are regarded as references. Such references can be detected by a process of disassembly applied on the program or, if given, by analyzing a relocation table attached to executable programs by link-editors that create them.
Another example of a data table is a group of inter-linked data records stored in an array of bytes where records contain addresses of other data records. The format of the records and the way they are laid out in the array are known, and the analysis and decomposition of such array is possible.
Old programxe2x80x94an example of old data table: a program (or portion of a program) that is to be updated so as to generate a new program (or portion of a program).
It should be further noted that reference to the old program and the new program is made for convenience of explanation only, and encompasses inter alia the upgrade of the old program to the new program (e.g. due to an upgrade in versions), modifications of the old program to the new program, (e.g. due to corrections of bugs in the old program), and changing from a first old program to a second (and possibly different) new program;
For convenience of explanation, the invention is described with reference to a specific example of computer programs. The invention is by no means bound by this particular example.
As explained above, applying a known per se file difference utility to an old program and a new program normally results in a relatively large amount of data, even if the modifications that were introduced to the old program (in order to generate the new program) are very few. The present invention is based on the observation that the relatively large size of the difference result stems from the alterations of reference in reference entries as a result of other newly inserted entries (and/or entries that were deleted).
On the basis of this observation, the invention aims at generating a modified old program and a modified new program, wherein the difference in references in corresponding entries in said new and old programs as explained above, will be reflected as invariant entries in the modified old and new programs. The net effect is that the invariant reference entries (between the modified old program and the modified new program), will not appear in the difference result, thereby reducing its size as compared to a conventional difference result obtained by using hitherto known techniques.
Accordingly, the invention provides for a method for generating a compact difference result between an old program and a new program; each program including reference entries that contain reference that refer to other entries in the program; the method comprising the steps of:
(a) scanning the old program and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby a modified old program is generated;
(b) scanning the new program and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby a modified new program is generated;
(c) generating said difference result utilizing directly or indirectly at least said modified old program and modified new program.
The invention further provides for a method for performing an update in an old program so as to generate a new program; each program including reference entries that contain reference that refer to other entries in the program; the method comprising the steps of:
(a) receiving data that includes a compact difference result; said compact difference result was generated utilizing a modified old program and a modified new program;
(b) scanning the old program and for substantially each reference entry perform, steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby the modified old program is generated;
(c) reconstituting the modified new program utilizing at least said compact difference result and said modified old program; said modified new program is differed from said new program at least in that substantially each reference entry in said new program is replaced in said modified new program by a distinct label mark;
(d) reconstituting said new program utilizing directly or indirectly at least said compact difference result and said modified new program.
Still further, the invention provides for a method for generating a compact difference result between an old program, and a new program; each program including reference entries that contain reference that refer to other entries in the program; the method comprising the steps of:
(a) generating a modified old program utilizing at least said old program;
(b) generating a modified new program utilizing at least said new program, said modified old program and modified new program have at least the following characteristics:
(i) substantially each reference in an entry in said old program that is different than corresponding entry in said new program due to delete/insert modifications that form part of the transition between said old program and new program are reflected as invariant references in the corresponding entries in said modified old and modified new programs;
(c) generating said compact difference result utilizing at least said modified new program and modified old program.
Yet further, the invention provides for a method for performing an update in an old program so as to generate a new program; each program including reference entries that contain reference that refer to other entries in the program; the method comprising the steps of:
(a) receiving data that includes a compact difference result; said compact difference result was generated utilizing a modified old program and a modified new program;
(b) generating a modified old program utilizing at least said old program;
(c) reconstituting a modified new program utilizing directly or indirectly at least said modified old program and said compact difference result; said modified old program and modified new program have at least the following characteristics:
(i) substantially each reference in an entry in said old program that is different than corresponding entry in said new program due to delete/inset modifications that form part of the transition between said old program and new programs are reflected as invariant references in the corresponding entries in said modified old and modified new programs;
(d) reconstituting said new program utilizing directly or indirectly at least said compact difference result and said modified new program.
According to another aspect, the invention provides for a system for generating a compact difference result between an old program and a new program; each program including reference entries that contain reference that refer to other entries in the program; the system comprising a processing device capable of:
(a) scanning the old program and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby a modified old program is generated;
(b) scanning the new program and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby a modified new program is generated;
(c) generating said difference result utilizing directly or indirectly at least said modified old program and modified new program.
Still further, the invention provides for a system for performing an update in an old program so as to generate a new program; each program including reference entries that contain reference that refer to other entries in the program; the system comprising a processing device capable of:
(a) receiving data that includes a compact difference result; said compact difference result was generated utilizing a modified old program and a modified new program;
(b) scanning the old program and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby the modified old program is generated;
(c) reconstituting the modified new program utilizing at least said compact difference result and said modified old program; said modified new program is differed from said new program at least in that substantially each reference entry in said new program is replaced in said modified new program by a distinct label mark;
(d) reconstituting said new program utilizing directly or indirectly at least said compact difference result and said modified new program.
The invention further provides for a system for generating a compact difference result between an old program and a new program; each program including reference entries that contain reference that refer to other entries in the program; the system comprising a processing device capable of:
(a) generating a modified old program utilizing at least said old program;
(b) generating a modified new program utilizing at least said new program, said modified old program and modified new program have at least the following characteristics:
(i) substantially each reference in an entry in said old program that is different than corresponding entry in said new program due to delete/insert modifications that form part of the transition between said old program and new program are reflected as invariant references in the corresponding entries in said modified old and modified new programs;
(c) generating said compact difference result utilizing at least said modified new program and modified old program.
Still further, the invention provides for a system for performing an update in an old program so as to generate a new program; each program including reference entries that contain reference that refer to other entries in the program; the system comprising a processing device capable of:
(a) receiving data that includes a compact difference result; said compact difference result was generated utilizing a modified old program and a modified new program;
(b) generating a modified old program utilizing at least said old program;
(c) reconstituting a modified new program utilizing directly or indirectly at least said modified old program and said compact difference result; said modified old program and modified new program have at least the following characteristics:
(i) substantially each reference in an entry in said old program that is different than corresponding entry in said new program due to delete/inset modifications that form part of the transition between said old program and new program are reflected as invariant references in the corresponding entries in said modified old and modified new programs;
(d) reconstituting said new program utilizing directly or indirectly at least said compact difference result and said modified new program.
Yet further, the invention provides for a method for generating a compact difference result between an old data table and a new data table; each data table including reference entries that contain reference that refer to other entries in the data table; the method comprising the steps of:
(a) scanning the old data table and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby a modified old data table is generated;
(b) scanning the new data table and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby a modified new data table is generated;
(c) generating said difference result utilizing directly or indirectly at least said modified old data table and modified new data table.
Moreover, the invention provides for a method for performing an update in an old data table so as to generate a new data table; each data table including reference entries that contain reference that refer to other entries in the data table; the method comprising the steps of:
(a) receiving data that includes a compact difference result; said compact difference result was generated utilizing a modified old data table and a modified new data table;
(b) scanning the old data table and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby the modified old data table is generated;
(c) reconstituting the modified new data table utilizing at least said compact difference result and said modified old data table; said modified new data table is differed from said new data table at least in that substantially each reference entry in said new data table is replaced in said modified new data table by a distinct label mark;
(d) reconstituting said new data table utilizing directly or indirectly at least said compact difference result and said modified new data table.
The invention her provides for a method for generating a compact difference result between an old data table and a new data table; each data table including reference entries that contain reference that refer to other entries in the data table; the method comprising the steps of:
(a) generating a modified old data table utilizing at least said old data table;
(b) generating a modified new data table utilizing at least said new data table, said modified old data table and modified new data table have at least the following characteristics:
(i) substantially each reference in an entry in said old data table that is different than corresponding entry in said new data table due to delete/insert modifications that form part of the transition between said old data table and new data table are reflected as invariant references in the corresponding entries in said modified old and modified new data tables;
(c) generating said compact difference result utilizing at least said modified new data table and modified old data table.
The invention provides for a method for performing an update in an old data table so as to generate a new data table; each data table including reference entries that contain reference that refer to other entries in the data table; the method comprising the steps of:
(a) receiving data that includes a compact difference result; said compact difference result was generated utilizing a modified old data table and a modified new data table;
(b) generating a modified old data table utilizing at least said old data table;
(c) reconstituting a modified new data table utilizing directly or indirectly at least said modified old data table and said compact difference result; said modified old data table and modified new data table have at least the following characteristics:
(i) substantially each reference in an entry in said old data table that is different than corresponding entry in said new data table due to delete/inset modifications that form part of the transition between said old data table and new data table are reflected as invariant references in the corresponding entries in said modified old and modified new data tables;
(d) reconstituting said new data table utilizing directly or indirectly at least said compact difference result and said modified new data table.
The invention further provides for a system for generating a compact difference result between an old data table and a new data table; each data table including reference entries that contain reference that refer to other entries in the data table; the system comprising a processing device capable of:
(a) scanning the old data table and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby a modified old data table is generated;
(b) scanning the new data table and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby a modified new data table is generated;
(c) generating said difference result utilizing directly or indirectly at least said modified old data able and modified new data table.
Still further, the invention provides for a system for performing an update in an old data table so as to generate a new data table; each data table including reference entries that contain reference that refer to other entries in the data table; the system comprising a processing device capable of:
(a) receiving data that includes a compact difference result; said compact difference result was generated utilizing a modified old data table and a modified new data table;
(b) scanning the old data table and for substantially each reference entry perform steps that include:
(i) replacing the reference of said entry by a distinct label mark, whereby the modified old data table is generated;
(c) reconstituting the modified new data table utilizing at least said compact difference result and said modified old data table; said modified new data table is differed from said new data table at least in that substantially each reference entry in said new data table is replaced in said modified new data table by a distinct label mark;
(d) reconstituting said new data table utilizing directly or indirectly at least said compact difference result and said modified new data table.
Moreover, the invention provides for a system for generating a compact difference result between an old data table and a new data table; each data table including reference entries that contain reference that refer to other entries in the data table; the system comprising a processing device capable of:
(a) generating a modified old data table utilizing at least said old data table;
(b) generating a modified new data table utilizing at least said new data table, said modified old data table and modified new data table have at least the following characteristics:
(i) substantially each reference in an entry in said old data table that is different than corresponding entry in said new data table due to delete/insert modifications that form part of the transition between said old data table and new data table are reflected as invariant references in the corresponding entries in said modified old and modified new data tables;
(c) generating said compact difference result utilizing at least said modified new data table and modified old data table.
The invention provides for a system for performing an update in an old data table so as to generate a new data table; each data table including reference entries that contain reference that refer to other entries in the data table; the system comprising a processing device capable of:
(a) receiving data that includes a compact difference result; said compact difference result was generated utilizing a modified old data table and a modified new data table;
(b) generating a modified old data table utilizing at least said old data table;
(c) reconstituting a modified new data table utilizing directly or indirectly at least said modified old data table and said compact difference result; said modified old data table and modified new data table have at least the following characteristics:
(i) substantially each reference in an entry in said old data table that is different than corresponding entry in said new data table due to deleted/inset modifications that form part of the transition between said old data table and new data table are reflected as invariant references in the corresponding entries in said modified old and modified new data tables;
(d) reconstituting said new data table utilizing directly or indirectly at least said compact difference result and said modified new data table.